package com.lx.algorithm.code;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-01 15:06:46
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-01     张李鑫                     1.0         1.0 Version
 */
public class Code11 {

    /**
     * 给定一个数组arr,已知其中所有的值都是非负的,将这个数组看作一个容器, 请返回容器能装多少水
     * 比如,arr = {3,1,2,5,2,4},根据值画出的直方图就是容器形状,该容 器可以装下5格水
     * 再比如,arr = {4,5,1,3,2},该容器可以装下2格水
     *
     * @param arr
     * @return
     */

    /**
     * 不使用辅助数组进行统计
     * @param arr
     * @return
     */
    public static int maxWater(int[] arr) {
        //两个指针 默认从边界+ -一的位置走 因为边界是不统计水的
        int n = arr.length;
        int lMax = arr[0];
        int rMax = arr[n - 1];

        int l = 1;
        int r = arr.length - 2;
        int sum = 0;

        //还没有走完
        while (l <= r) {
            //算出左右的值谁小
            int min = Math.min(lMax, rMax);
            //如果左边最大值小于右边界左边走 否则右边走 走完都要更新一下最大值
            if (lMax < rMax) {
                sum += Math.max(0, min - arr[l]);
                lMax = Math.max(arr[l], lMax);
                l++;
            } else {
                sum += Math.max(0, min - arr[r]);
                rMax = Math.max(arr[r], rMax);
                r--;
            }
        }
        return sum;
    }


}